//////////////////////////////////////
// Fast Container Library           //
// MIT License - Copyright (c) 2012 //
//////////////////////////////////////

#pragma once

#include "allocator.h"
#include "basic_string_ref.h"
#include "forward.h"

#ifdef _MSC_VER
	#pragma warning ( push )
	#pragma warning ( disable : 4480 )
	#pragma warning ( disable : 4996 )
#endif

#include <cstdarg> //for va_list

FC_NAMESPACE_BEGIN


template <class T, class Allocator>
class basic_string : public basic_string_ref<T>
{
public:
	typedef Allocator									allocator_type;
	typedef basic_string<T, Allocator>					this_type;
	typedef basic_string_ref<T>							base_type;
	typedef char_traits<T>								traits_type;
	typedef typename base_type::iterator				iterator;
	typedef typename base_type::const_iterator			const_iterator;

	using base_type::npos;
	using base_type::maxsize;
	using base_type::find;
	using base_type::rfind;
	using base_type::find_first_of;
	using base_type::find_first_not_of;
	using base_type::find_last_of;
	using base_type::find_last_not_of;
	using base_type::compare;
	using base_type::empty;
	using base_type::size;
	using base_type::length;
	using base_type::operator [];
	using base_type::at;
	using base_type::front;
	using base_type::back;
	using base_type::begin;
	using base_type::end;
	using base_type::rbegin;
	using base_type::rend;
	using base_type::data;
	using base_type::c_str;

	using base_type::m_begin;
	using base_type::m_end;

	basic_string()
		: base_type(), m_capacity(0), m_allocator()
		{
			InitializeBuffer();
		}

	explicit basic_string( const allocator_type& alloc )
		: base_type(), m_capacity(0), m_allocator(alloc)
		{
			InitializeBuffer();
		}

	basic_string( uninitialized_construct, const allocator_type& alloc )
		: base_type(), m_capacity(0), m_allocator(alloc)
		{
			//empty
		}

	basic_string( uninitialized_construct, size_t reserveCapacity, size_t /*flags*/ = 0 )
		: base_type(), m_capacity(0), m_allocator()
		{
			InitializeCapacity(reserveCapacity);
		}

	explicit basic_string( T c )
		: base_type(), m_capacity(0), m_allocator()
		{
			append( c );
		}

	basic_string( const T* s, size_t n, const allocator_type& alloc = allocator_type() )
		: base_type(), m_capacity(0), m_allocator(alloc)
		{
			InitializeCapacity(n);
			append_unchecked(s, n);
		}

	basic_string( const T* s )
		: base_type(), m_capacity(0), m_allocator()
		{
			const size_t n = traits_type::length(s);
			InitializeCapacity(n);
			append_unchecked(s, n);
		}

	basic_string( size_t n, T c, const allocator_type& alloc = allocator_type() )
		: base_type(), m_capacity(0), m_allocator(alloc)
		{
			InitializeCapacity(n);
			append_unchecked(n, c);
		}

	basic_string( const this_type& str )
		: base_type(), m_capacity(0), m_allocator()
		{
			InitializeCapacity( size_t(str.m_end - str.m_begin) );
			append_unchecked( str.m_begin, str.m_end );
		}

	basic_string( const base_type& str )
		: base_type(), m_capacity(0), m_allocator()
		{
			InitializeCapacity( size_t(str.m_end - str.m_begin) );
			append_unchecked( str.m_begin, str.m_end );
		}

	basic_string( const base_type& str, size_t pos, size_t n = npos )
		: base_type(), m_capacity(0), m_allocator()
		{
			const_iterator first = str.m_begin + pos;
			const_iterator last = (n == npos ? str.m_end : str.m_begin + pos + n);
			InitializeCapacity( size_t(last - first) );
			append_unchecked( first, last );
		}

	basic_string( const_iterator first, const_iterator last )
		: base_type(), m_capacity(0), m_allocator()
		{
			InitializeCapacity( size_t(last - first) );
			append_unchecked( first, last );
		}

	basic_string( size_t bufferLength, const char* format, ... )
		: base_type(), m_capacity(0), m_allocator()
		{
			va_list args;
			va_start(args, format);
			append_args( bufferLength, format, args );
			va_end(args);
		}

	~basic_string()
		{
			deallocate();
		}

	size_t capacity() const	{ return size_t(m_capacity - m_begin); }
	size_t max_size() const	{ return maxsize; }
	size_t unused() const	{ return size_type(m_capacity - (m_end - 1)); }

	allocator_type& get_allocator() { return m_allocator; }
	void set_allocator( const allocator_type& alloc ) { m_allocator = alloc; }

	void remove_prefix( size_t n ) { erase(m_begin, m_begin + n); }
	void remove_suffix( size_t n ) { erase(m_end - n, m_end); }
	void pop_front() { erase(m_begin); }

	void swap( this_type& x )
	{
		if( m_allocator == x.m_allocator )
		{
			fc::swap( m_begin, x.m_begin );
			fc::swap( m_end, x.m_end );
			fc::swap( m_capacity, x.m_capacity );
		}
		else
		{
			this_type temp(*this);
			*this = x;
			x = temp;
		}
	}

	//template <class U>
	//this_type& operator =( const basic_string<T, U>& str ) { return assign( str.m_begin, str.m_end ); }
	this_type& operator =( const this_type& str )	{ return assign( str.m_begin, str.m_end ); }
	this_type& operator =( const base_type& str )	{ return assign( str.m_begin, str.m_end ); }
	this_type& operator =( const T* s )				{ return assign( s, s + traits_type::length(s) ); }
	this_type& operator =( T c )					{ return assign( size_t(1), c ); }

	this_type& assign( const T* s, size_t n )	{ return assign( s, s + n ); }
	this_type& assign( const T* s )				{ return assign( s, s + traits_type::length(s) ); }

	this_type& assign( const base_type& str )	{ return assign( str.m_begin, str.m_end ); }
	this_type& assign( const base_type& str, size_t pos, size_t n ) { return assign( str.m_begin + pos, str.m_begin + pos + n ); }

	this_type& assign( size_t n, T c )
	{
		clear();
		return append( n, c );
	}

	this_type& assign( const_iterator first, const_iterator last )
	{
		clear();
		return append( first, last );
	}

	this_type& assign( size_t bufferLength, const char* format, ... )
	{
		va_list args;
		va_start(args, format);
		clear();
		append_args( bufferLength, format, args );
		va_end(args);

		return *this;
	}

	void resize( size_t n, T c = T(0) )
	{
		const size_t thisSize = size();
		if( n > thisSize )
			insert( m_end, n - thisSize, c );
		else if( n < thisSize )
			erase( m_begin + n, end() );
	}

	void reserve( size_t n = 0 )
	{
		if( n > capacity() )
			set_capacity(n + 1);
	}

	void shrink_to_fit() { set_capacity( size() ); }
	void set_capacity( size_t newCapacity )
	{
		if( newCapacity == capacity() )
			return;

		T* ptr = allocate(newCapacity);
		const size_t thisSize = size();
		const size_t n = thisSize > newCapacity ? newCapacity : thisSize;

		if(m_capacity)
		{
			traits_type::copy( ptr, m_begin, n );
			deallocate();
		}

		m_begin = ptr;
		m_end = m_begin + n;
		m_capacity = m_begin + newCapacity;
		*m_end = T(0);
	}

	this_type& operator +=( const base_type& str ) { return append( str.m_begin, str.m_end ); }
	this_type& operator +=( const T* s ) { return append(s, traits_type::length(s)); }
	this_type& operator +=( T c ) { push_back(c); return *this; }

	this_type& append( const T* s ) { return append(s, traits_type::length(s)); }
	this_type& append( const T* s, size_t n )
	{
		if( n > 0 )
		{
			assure_capacity(n);
			append_unchecked(s, n);
		}
		return *this;
	}

	this_type& append( const base_type& str ) { return append( str.m_begin, str.m_end ); }
	this_type& append( const base_type& str, size_t pos, size_t n )
	{
		return append( str.m_begin + pos, str.m_begin + pos + n );
	}

	this_type& append( T c ) { push_back(c); return *this; }
	this_type& append( size_t n, T c )
	{
		if( n > 0 )
		{
			assure_capacity(n);
			append_unchecked(n, c);
		}
		return *this;
	}

	this_type& append( const_iterator first, const_iterator last )
	{
		FC_ASSERT(first <= last);
		const size_t n = size_t(last - first);
		if( n > 0 )
		{
			assure_capacity(n);
			append_unchecked(first, n);
		}
		return *this;
	}

	this_type& append( size_t n, const char* format, ... )
	{
		va_list args;
		va_start(args, format);
		append_args(n, format, args);
		va_end(args);

		return *this;
	}

	this_type& assign_unchecked( const T* s )			{ clear(); return append_unchecked( s, traits_type::length(s) ); }
	this_type& assign_unchecked( const T* s, size_t n )	{ clear(); return append_unchecked( s, n ); }
	this_type& assign_unchecked( const base_type& str )	{ clear(); return append_unchecked( str.m_begin, str.m_end ); }
	this_type& assign_unchecked( const base_type& str, size_t pos, size_t n )
	{
		clear();
		return append_unchecked( str.m_begin + pos, str.m_begin + pos + n );
	}

	this_type& assign_unchecked( size_t n, T c )
	{
		clear();
		return append_unchecked( n, c );
	}

	this_type& assign_unchecked( const_iterator first, const_iterator last )
	{
		clear();
		return append_unchecked( first, last );
	}

	this_type& append_unchecked( const T* s ) { return append_unchecked(s, traits_type::length(s)); }
	this_type& append_unchecked( const T* s, size_t n )
	{
		traits_type::copy(m_end, s, n);
		m_end += n;
		*m_end = T(0);
		return *this;
	}

	this_type& append_unchecked( const base_type& str ) { return append_unchecked( str.m_begin, str.m_end ); }
	this_type& append_unchecked( const base_type& str, size_t pos, size_t n )
	{
		return append_unchecked( str.m_begin + pos, str.m_begin + pos + n );
	}

	this_type& append_unchecked( T c ) { push_back_unchecked(c); return *this; }
	this_type& append_unchecked( size_t n, T c )
	{
		traits_type::assign( m_end, n, c );
		m_end += n;
		*m_end = T(0);
		return *this;
	}

	this_type& append_unchecked( const_iterator first, const_iterator last )
	{
		const size_t n = size_t(last - first);
		traits_type::copy(m_end, first, n);
		m_end += n;
		*m_end = T(0);
		return *this;
	}

	void push_back_unchecked( T c )
	{
		*m_end = c;
		*++m_end = T(0);
	}

	void push_back( T c )
	{
		assure_capacity( size_t(1) );
		push_back_unchecked(c);
	}

	void pop_back()
	{
		FC_ASSERT(!empty());
		*--m_end = T(0);
	}


	this_type& insert( size_t pos, const base_type& str )
	{
		insert( m_begin + pos, str.m_begin, str.m_end );
		return *this;
	}

	this_type& insert( size_t pos, const base_type& str, size_t beg, size_t n )
	{
		insert( m_begin + pos, str.m_begin + beg, str.m_begin + beg + n );
		return *this;
	}

	this_type& insert( size_t pos, const T* s, size_t n )
	{
		insert( m_begin + pos, s, s + n );
		return *this;
	}

	this_type& insert( size_t pos, const T* s )
	{
		insert( m_begin + pos, s, s + traits_type::length(s) );
		return *this;
	}

	void insert( iterator it, const_iterator first, const_iterator last )
	{
		FC_ASSERT(iterator_is_valid(it));
		FC_ASSERT(first <= last);
		if( iterator_is_valid(first) && last > it )
		{
			//if we're inserting from ourself we have to create a temp object and recurse.
			this_type temp(first, last);
			insert( it, temp.m_begin, temp.m_end );
			return;
		}

		//size_t pos = it - m_begin;
		size_t n = size_t(last - first);
		if( n > 0 )
		{
			if( m_end + n + 1 >= m_capacity )
			{
				size_t cap = calculate_new_capacity(n);
				T* ptr = allocate(cap);
				size_t thisSize = size();
				size_t d = size_t(it - m_begin);

				traits_type::copy( ptr, m_begin, d );
				traits_type::copy( ptr + d, first, n );
				traits_type::copy( ptr + d + n, m_begin + d, thisSize - d );

				deallocate();
				m_begin = ptr;
				m_end = m_begin + thisSize;
				m_capacity = m_begin + cap;
			}
			else
			if( it == m_end )
			{
				traits_type::copy( m_end, first, n );
			}
			else
			{
				traits_type::move( it + n, it, size_t(m_end - it) );
				traits_type::copy( it, first, n );
			}

			m_end += n;
			*m_end = T(0);
		}
	}

	iterator insert( iterator it, T c ) { size_t pos = size_t(it - m_begin); insert( pos, size_t(1), c ); return m_begin + pos; }
	void insert( size_t pos, T c ) { insert( pos, size_t(1), c ); }
	void insert( iterator it, size_t n, T c ) { insert( it - m_begin, n, c ); }
	this_type& insert( size_t pos, size_t n, T c )
	{
		FC_ASSERT(pos <= size());
		if( n > 0 )
		{
			if( m_end + n + 1 >= m_capacity )
			{
				size_t cap = calculate_new_capacity(n);
				T* ptr = allocate(cap);
				size_t thisSize = size();

				traits_type::copy( ptr, m_begin, pos );
				traits_type::assign( ptr + pos, n, c );
				traits_type::copy( ptr, m_begin + pos, thisSize - pos );

				deallocate();
				m_begin = ptr;
				m_end = m_begin + thisSize;// + n; //we already add n
				m_capacity = m_begin + cap;
				//*m_end = T(0);
			}
			else
			if( m_begin + pos == m_end )
			{
				traits_type::assign( m_end, n, c );
			}
			else
			{
				iterator first = m_begin + pos;
				iterator last = first + n;
				traits_type::move( last, first, size_t(m_end - first) );
				traits_type::assign( first, n, c );
			}

			m_end += n;
			*m_end = T(0);
		}

		return *this;
	}


	this_type& erase( size_t pos = 0, size_t n = npos )
	{
		erase( m_begin + pos, (n == npos ? m_end : m_begin + pos + n) );
		return *this;
	}

	iterator erase( iterator it )
	{
		FC_ASSERT(iterator_is_valid(it));

		if( it == m_end - 1 )
			pop_back();
		else
		{
			traits_type::move( it, it + 1, size_t(m_end - it) );
			--m_end;
		}

		return it;
	}

	iterator erase( iterator first, iterator last )
	{
		FC_ASSERT(iterator_is_valid(first) && iterator_is_valid(last));
		if( first != last )
		{
			size_t n = size_t(m_end - last);
			size_t diff = size_t(last - first);

			if( n < diff )
				traits_type::copy( first, last, n + 1 );
			else
				traits_type::move( first, last, n + 1 );

			m_end -= diff;
		}
		return first;
	}

	void clear()
	{
		if(m_begin != m_end)
			*m_begin = T(0), m_end = m_begin;
	}

	this_type substr( size_t pos = 0, size_t n = npos ) const
	{
		const_iterator first = m_begin + pos;
		const_iterator last = (n > size() ? m_end : first + n);
		FC_ASSERT(iterator_is_valid(first) && iterator_is_valid(last) && first <= last);
		return this_type(first, last);
	}

	this_type substr( const_iterator first, const_iterator last ) const
	{
		FC_ASSERT(iterator_is_valid(first) && iterator_is_valid(last) && first <= last);
		return this_type(first, last);
	}

	base_type substr_ref( size_t pos = 0, size_t n = npos ) const
	{
		const_iterator first = m_begin + pos;
		const_iterator last = (n > size() ? m_end : first + n);
		FC_ASSERT(iterator_is_valid(first) && iterator_is_valid(last) && first <= last);
		return base_type(first, last);
	}

	base_type substr_ref( const_iterator first, const_iterator last ) const
	{
		FC_ASSERT(iterator_is_valid(first) && iterator_is_valid(last) && first <= last);
		return base_type(first, last);
	}


	this_type& replace( iterator first, iterator last, const base_type& str ) { return replace( first, last, str.m_begin, str.m_end ); }
	this_type& replace( iterator first, iterator last, const T* s, size_t n ) { return replace( first, last, s, s + n ); }
	this_type& replace( iterator first, iterator last, const T* s ) { return replace( first, last, s, s + traits_type::length(s) ); }
	this_type& replace( size_t pos, size_t n, const T* s, size_t len ) { return replace( m_begin + pos, m_begin + pos + n, s, s + len ); }
	this_type& replace( size_t pos, size_t n, const T* s ) { return replace( m_begin + pos, m_begin + pos + n, s, s + traits_type::length(s) ); }
	this_type& replace( size_t pos, size_t n, const base_type& str ) { return replace( m_begin + pos, m_begin + pos + n, str.m_begin, str.m_end ); }
	this_type& replace( size_t pos, size_t n, const base_type& str, size_t beg, size_t len )
	{
		return replace( m_begin + pos, m_begin + pos + n,
			str.m_begin + beg, str.m_begin + beg + len );
	}

	this_type& replace( iterator first1, iterator last1, const_iterator first2, const_iterator last2 )
	{
		FC_ASSERT(iterator_is_valid(first1) && iterator_is_valid(last1));
		FC_ASSERT(first1 <= last1 && first2 <= last2);

		const size_t n1 = size_t(last1 - first1);
		const size_t n2 = size_t(last2 - first2);
		size_t difference(0);

		this_type self;
		if( first2 > first1 && first1 < m_end )
		{
			self.assign(first2, last2);
			first2 = self.m_begin;
			last2 = self.m_end;
		}

		if( n2 > n1 )
		{
			difference = n2 - n1;
			assure_capacity( difference );
			traits_type::move( first1 + n2, last1, size_t(m_end - last1) );
			traits_type::move( first1, first2, n2 );

			m_end += difference;
			*m_end = T(0);
		}
		else if( n1 > n2 )
		{
			difference = n1 - n2;
			traits_type::move( first1 + n2, last1, size_t(m_end - last1) );
			traits_type::move( first1, first2, n2 );

			m_end -= difference;
			*m_end = T(0);
		}
		else
		{
			traits_type::move( first1, first2, n2 );
		}

		return *this;
	}

	this_type& replace( size_t pos, size_t n, size_t amount, T c ) { return replace( m_begin + pos, m_begin + pos + n, amount, c ); }
	this_type& replace( iterator first, iterator last, size_t n, T c )
	{
		FC_ASSERT(iterator_is_valid(first) && iterator_is_valid(last));
		FC_ASSERT(first <= last);
		const size_t replaceSize = size_t(last - first);
		const size_t minNum = fc::min( replaceSize, n );

		if( minNum > 0 )
			traits_type::assign( first, minNum, c );

		if( n < replaceSize )
			erase( first + n, first + replaceSize );
		else if( replaceSize < n )
			insert( last, n - replaceSize, c );

		return *this;
	}

	size_t copy( T* s, size_t n, size_t pos = 0 ) const
	{
		const size_t thisSize = size_t(m_end - m_begin);
		if( pos > thisSize )
			return size_t(0);

		const size_t len = fc::min(n, thisSize - pos);
		traits_type::copy( s, m_begin + pos, len );
		return len;
	}

	this_type& append_args( size_t n, const char* format, va_list args )
	{
		assure_capacity(n);
		int retVal = vsnprintf( m_end, size_t(m_capacity - m_end), format, args );
		if( retVal > 0 )
			m_end += retVal, *m_end = T(0);

		return *this;
	}

	this_type& append_int( int value ) { return append( size() + 16, "%i", value ); }
	this_type& append_float( float value ) { return append( size() + 16, "%f", value ); }

	this_type to_upper() { return this_type(*this).make_upper(); }
	this_type to_upper( size_t pos, size_t n ) { return this_type(*this).make_upper(pos, n); }

	this_type to_lower() const { return this_type(*this).make_lower(); }
	this_type to_lower( size_t pos, size_t n ) const { return this_type(*this).make_lower(pos, n); }

	this_type& make_upper() { return (this_type&)base_type::make_upper(); }
	this_type& make_upper( size_t pos, size_t n ) { fc::make_upper( m_begin + pos, m_begin + pos + n ); return *this; }

	this_type& make_lower() { return (this_type&)base_type::make_lower(); }
	this_type& make_lower( size_t pos, size_t n ) { fc::make_lower( m_begin + pos, m_begin + pos + n ); return *this; }

	int to_int() const { return to_int( m_begin, size_t(0) ); }
	int to_int( size_t pos ) const { return to_int( m_begin, pos ); }
	float to_float() const { return to_float( m_begin, size_t(0) ); }
	float to_float( size_t pos ) const { return to_float( m_begin, pos ); }
	double to_double() const { return to_double( m_begin, size_t(0) ); }
	double to_double( size_t pos ) const { return to_double( m_begin, pos ); }

	static int to_int( const char* s, size_t pos = size_t(0) ) { return fc::to_int( s + pos, 0 ); }
	static float to_float( const char* s, size_t pos = size_t(0) ) { return fc::to_float( s + pos, 0 ); }
	static double to_double( const char* s, size_t pos = size_t(0) ) { return fc::to_double( s + pos, 0 ); }

	static size_t string_length( const T* s )
	{
		return (s ? traits_type::length(s) : size_t(0));
	}

	bool iterator_is_valid( const_iterator it ) const
	{
		return (it >= m_begin && it <= m_end);
	}

	size_t get_hash() const
	{
		return fnv_hash(c_str(), size());
	}

	void grow( size_t amount )
	{
		size_t newCap = calculate_new_capacity(amount);
		set_capacity(newCap);
	}

protected:
	T* allocate( size_t n )
	{
		return (T*)m_allocator.allocate( n * sizeof(T) );
	}

	void deallocate()
	{
		// if( m_begin && m_begin == _StaticStringBuffer ) and the string has a capacity of 1,
		// then it points to a static buffer whose value should be 0. (null-terminated empty string)
		if( m_begin && m_capacity != m_begin + 1 )
			m_allocator.deallocate( m_begin, size_t(m_end - m_begin) * sizeof(T) );
	}

	void assure_capacity( size_t n )
	{
		if( m_end + n + 1 >= m_capacity )
			grow(n);
	}

	inline size_t calculate_new_capacity( size_t growth )
	{
		//grow by at least double to avoid more reallocations.
		size_t oldCap = capacity();
		return fc::max( fc::max<size_t>( oldCap * 2, oldCap + growth + 1 ), size_t(32) );
	}


	// The c++ standard require that an uninitialized string return a null-terminated
	// sequence of T, or "", and not null, or even worse, users rely on bad code such as
	// "string uninitializedString; if( uninitializedString[0] == '\0' );" ...
	// If this behavior is enabled then all strings must be initialized to an internal
	// empty buffer in order to be compliant.

	#if FC_USE_SSO_STRINGS
		void InitializeBuffer()
		{
			// initialize string to internal allocator buffer.
			m_begin = m_end = (T*)allocate(FC_DEFAULT_STRING_BUFFER_SIZE);
			m_capacity = m_begin + FC_DEFAULT_STRING_BUFFER_SIZE;
			*m_end = T(0);
		}
	#elif FC_REQUIRE_INITIALIZED_STRINGS
		static const int _StaticStringBuffer = 0;

		void InitializeBuffer()
		{
			FC_ASSERT(_StaticStringBuffer == 0);
			m_begin = m_end = (T*)&_StaticStringBuffer;
			m_capacity = m_begin + 1;
		}
	#else
		void InitializeBuffer(){} //empty
	#endif

	void InitializeCapacity( size_t n )
	{
		if( n > 0 )
		{
			n += 1;
			T* newBegin = allocate(n);

			m_begin = newBegin;
			m_end = newBegin;
			m_capacity = newBegin + n;
			*m_end = T(0);
		}
		else
		{
			// by default we have to initialize to buffer.
			InitializeBuffer();
		}
	}

	T* m_capacity;
	allocator_type m_allocator;

};




// global operators

template <class T, class Allocator> inline
	void swap( basic_string<T, Allocator>& a, basic_string<T, Allocator>& b )
	{
		a.swap(b);
	}

template <class T, class Allocator> inline
	void swap( basic_string<T, Allocator>& a, basic_string_ref<T>& b )
	{
		// There's no reasonable way to handle this.
		b = a;
	}

template <class T, class Allocator> inline
	void swap( basic_string_ref<T>& a, basic_string<T, Allocator>& b )
	{
		// There's no reasonable way to handle this.
		a = b;
	}




#ifdef _MSC_VER
	#pragma warning ( pop )
#endif


FC_NAMESPACE_END

